/*
3Sum Closest


Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. 
You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/
typedef __int32 uint32_t;


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}
/*

alpMap[1] = "A";
alpMap[2] = "B";
alpMap[3] = "C";
alpMap[4] = "D";
alpMap[5] = "E";
alpMap[6] = "F";
alpMap[7] = "G";
alpMap[8] = "H";
alpMap[9] = "I";
alpMap[10] = "J";
alpMap[11] = "K";
alpMap[12] = "L";
alpMap[13] = "M";
alpMap[14] = "N";
alpMap[15] = "O";
alpMap[16] = "P";
alpMap[17] = "Q";
alpMap[18] = "R";
alpMap[19] = "S";
alpMap[20] = "T";
alpMap[21] = "U";
alpMap[22] = "V";
alpMap[23] = "W";
alpMap[24] = "X";
alpMap[25] = "Y";
alpMap[26] = "Z";
*/

class Solution {
public:
	int threeSumClosest(vector<int> &num, int target) {
		vector< vector<int> > result;

		int len = num.size();
		if (len == 0)
		{
			return target;

		}
		if (len < 3)
		{
			for (int i = 0; i < len; i++)
			{
				target -= num[i];
			}

			return target;
		}


		vector<int> num2(num.begin(), num.end());
		
		sort(num2.begin(), num2.end());

		
		int targetAbs;
		int closetResult;
		int minResult;
		bool first = true;
		//vector<int> tmpRet(3);

		for (int i = 0; i < len-2; i++)
		{
			int l = i + 1;
			int r = len - 1;

			
			while (l<r)
			{
				int sum = num2[i] + num2[l] + num2[r];
				targetAbs = abs(sum-target);
				if (first)
				{
					closetResult = sum;
					minResult = targetAbs;
					first = false;
				}
				else
				{
					if (targetAbs<minResult)
					{
						minResult = targetAbs;
						closetResult = sum;
					}
				}

				if (sum<target)
				{
					l++;
				}
				else
				{
					r--;
				}



			}

		}
		return closetResult;
	}
};

class Solution1 {
public:
	vector<vector<int> > threeSum(vector<int> &num) {


		vector< vector<int> > result;

		int len = num.size();
		if (len < 3) return result;

		vector<int> num2(num.begin(), num.end());


		sort(num2.begin(), num2.end());       // sort  O(n*log(n))  


		vector<int> tmpRet(3);
		tmpRet[0] = num2[0] - 1;

		for (int i = 0; i < len - 2; i++){       // O(n*m)  
			int l = i + 1;
			int r = len - 1;

			if (num2[i] == tmpRet[0]) continue;
			tmpRet[0] = num2[i];

			while (l < r) {
				int sum2 = num2[l] + num2[r];
				if (num2[i] + sum2 == 0){
					tmpRet[1] = num2[l];
					tmpRet[2] = num2[r];

					result.push_back(tmpRet);

					while (num2[++l] == num2[l - 1] && l < r);   // remove same number  
					while (num2[--r] == num2[r + 1] && l < r);

				}
				else if (num2[i] + sum2 < 0){
					l++;
				}
				else {
					r--;
				}
			}
		}

		return result;
	}
};


int main(int argc, char* argv[])
{

	string a1 = "1", a2 = "2";
	cout << a1 + a2 << endl;
	cout << a2 + a1 << endl;


	int temp;
	vector<int> nums;


	for (int i = 1; i < argc; i++){


		cout << argv[i] << endl;
		temp = atoi(argv[i]);
		nums.push_back(temp);
	}






	vector<vector<int> > result;


	Solution s;
	//stackTree.push(p->left);
	//stackTree.push(p->right);

	//ListNode *headA = new ListNode(1);
	//ListNode *pa1 = new ListNode(2);
	//ListNode *pa2 = new ListNode(3);
	//headA->next = pa1;
	//pa1->next = pa2;

	//ListNode *headB = new ListNode(4);
	//ListNode *pa1 = new ListNode(2);
	//ListNode *pa2 = new ListNode(3);
	//headA->next = pa1;
	//pa1->next = pa2;

	result = s.threeSum(nums);
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i][1] << endl;
	}





	system("pause");
	return 0;
}